Drogi ekspresowe

Limit pamięci: 64 MB

W Bajtocji jest miast oraz dróg pomiędzy nimi. Ich jakość jest bardzo kiepska, a ze względu na brak funduszy drogi od dłuższego czasu nie były remontowane.

Mieszkańcy Bajtocji protestują, domagając się zamiany części dróg na nowe drogi ekspresowe. Król Bajtocji zarządził, że wybuduje drogi ekspresowe, ale pod jednym warunkiem. Wystarczy, że zostanie stworzony plan budowy, w którym z każdego z bajtockich miast będzie wychodziła nieparzysta liczba dróg ekspresowych. Drogi ekspresowe mogą być budowane tylko w miejscach dróg już istniejących.

Mieszkańcy poprosili Cię o pomoc w wybraniu odpowiednich dróg. Pomóż mieszkańcom i stwórz plan budowy dróg ekspresowych lub stwierdź, że taki plan nie istnieje. Jeśli występuje więcej niż jeden poprawny plan, to wystarczy że podasz dowolny z nich.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę zestawów danych. Dalej podawane są opisy kolejnych zestawów.

Pierwszy wiersz zestawu zawiera dwie liczby całkowite , (, ), oznaczające odpowiednio liczbę miast oraz liczbę dróg w Bajtocji. W następnych wierszach znajduje się opis połączeń pomiędzy miastami. Każdy wiersz zawiera dwie liczby całkowite , (), oznaczające, że miasta i są połączone drogą.

Możesz założyć, że suma we wszystkich zestawach danych nie przekracza , a suma nie przekracza .

W testach wartych łącznie puntków zachodzą dodatkowe warunki i .

Wyjście

Na standardowym wyjściu powinny się pojawić odpowiedzi dla kolejnych zestawów danych.

Odpowiedzią dla zestawu danych powinien być opis planu budowy dróg ekspresowych lub jedno słowo NIE w przypadku, gdy taki plan nie istnieje. Opis planu powinien zawierać w pierwszym wierszu jedną liczbę całkowitą , równą liczbie dróg, które będą zamienione na drogi ekspresowe. Następnych wierszy powinno opisywać drogi ekspresowe. Każdy wiersz powinien zawierać dwie liczby całkowite , oznaczające, że droga pomiędzy miastami i będzie zamieniona na drogę ekspresową.

Przykład

Dla danych wejściowych:

1
6 5
1 2
1 3
2 3
3 4
5 6

poprawną odpowiedzią jest:

4
1 3
2 3
3 4
5 6

Autor zadania: Jacek Tomasiewicz.